The present invention relates to computer network devices and more particularly to a method and apparatus for independently sizing output routing tables in a network switch.
In computer networks employing network switches, communication of information is routed through the network via network switches. In some connection based networks, such as asynchronous transfer mode (ATM) networks, communications between a source of information and a final destination are considered connections or circuits which comprise virtual paths over which the information flows. Multiple connections may utilize the same physical paths as the information flows through the network.
ATM switches typically include a plurality of ingress cards referred to as Input Modules for receiving ATM cells, a plurality of egress cards referred to as Output Modules for forwarding ATM cells over a communications link to a downstream computer network device and a switch fabric for selectively forwarding cells received at one of the ingress cards to one of the egress or output cards for transmission over the respective communication link. In some network switches, the ingress and egress functions are combined as a single Input Output Module (IO Module). Each IO Module typically has multiple ports for receiving and transmitting data units such as cells in an ATM network. Each of the ports can typically support multiple connections or circuits.
The switch fabric interconnects each ingress card with each egress card so that a cell received at any one of the ingress cards can be selectively forwarded to any one of the egress cards.
In an ATM network, the destination paths are identified by an address comprising a Virtual Path Identifier ("VPI") and a Virtual Connection Identifier ("VCI"). The VPI comprises 8 or 12 bits depending on whether the cell is configured for User-Network Interface (UNI) or Network-Node Interface (NNI) operation, respectively. The VCI comprises 16 bits. When a circuit is established at "call setup", ingress translation tables and egress translation tables are configured as an administrative function such that a cell associated with a specific connection will be properly routed through the switch and assigned a correct VPI/VCI destination address for forwarding. Due to the fact that accommodating the number of possible VPI/VCI address combinations would result in excessive and unnecessary hardware costs, typical network switches support a number of connection identifiers far less than the total number of possible identifiers. Accordingly, when a connection is established at call setup, the respective VPI/VCI address pertaining to a particular connection is mapped, within each relevant network switch, into an arbitrary connection identifier which is used within the switch to associate a received cell with the respective connection. The connection identifiers need not be the same from device to device within the network since they are used solely within the switch. More specifically, upon receipt of a cell at an Input Module, the VPI/VCI address is inspected and a connection identifier (connection ID) is assigned which may be prepended to the information payload. The connection identifier associates the VPI/VCI with the respective connection within the switch.
Cells received at a network switch are typically identified as either unicast cells or multicast cells. A unicast cell is a cell which is received at a single input port of an IO Module and is transmitted to only a single output port of an IO Module. A multicast cell is a cell which is received at a single port of an Input Module and is transmitted to at least two output ports of the network switch for forwarding. The output ports involved in a multicast transmission may be within one or more than one Output Module.
Different connection identifier types are typically employed internally within a network switch to signal how a cell is forwarded within a network switch. Unicast cells are normally assigned a Connection ID (CID) and Multicast Cells are typically identified with a Multicast Identifier (MID).
When a cell arrives at an input port of an Input Module, the VPI/VCI address is used as an index into an ingress translation table to generate the appropriate connection identifier such as a CID or a MID. After the cell is switched to the specified Output Module or Modules, the connection identifier is employed as an index into an egress translation or routing table to obtain the outgoing VPI/VCI associated with the respective connection identifier for purposes of cell forwarding.
Typical ATM switch implementations have a single memory address space that is subdivided into separate tables for the different types of circuit identifiers. For example if the total number of circuit identifiers is 64K, then the connections identifiers could be stored in tables as follows:
______________________________________ CIDs 0-16k-1 MIDs 16k-64k-1. ______________________________________
Such an allocation scheme is undesirable since it is not readily scalable. For example, if the requirements for the number of CIDs were to grow, the assignment of additional CIDs would come at the expense of allocated MIDs. Thus, known addressing techniques for accessing egress translation tables are deficient in that they fail to permit independent sizing of output routing tables containing information for respective connection identifier types.